#ifndef RASTER_H
#define RASTER_H

#include "predicate.h"
#include <vector>
#include <algorithm>

class Cell
{
public:
	int x, y;

	Cell()
	{
		Cell(Point());
	}

	Cell(const Point &p_): x(std::floor(p_.x)), y(std::floor(p_.y)) {}

	Cell(const Cell &c): x(c.x), y(c.y) {}

	bool operator<(const Cell &c) const
	{
		return x == c.x ? y < c.y : x < c.x;
	}
	
	bool operator==(const Cell &c) const
	{
		return x == c.x && y == c.y;
	}

	bool operator!=(const Cell &c) const
	{
		return !((*this) == c);
	}

	friend std::ostream& operator<<(std::ostream &s, const Cell &c)
	{
		return s << c.x << " " << c.y << "\n";
	}
};
class poly_iterator: public std::iterator<std::forward_iterator_tag, const Cell>
{
private:
	std::vector<Point> upper, lower;
	bool is_end, finished_r, finished;
	Cell up, lo, curr;
	int ui, li;

	void init()
	{
		ui = 0; 
		li = 0;
		up = Cell(upper[0]);
		lo = Cell(lower[0]);
		init_bounds();
		curr = lo;
	}
	
	int get_maxy(const Point &p1, const Point &p2, int x1, int x2)
	{
		bool exact;
		int res = get_max_y(p1, p2, x1, x2, exact);

		if (exact)
		{
			res--;
		}

		return res;
	}
	
	int get_miny(const Point &p1, const Point &p2, int x1, int x2)
	{
		bool exact;
		return get_min_y(p1, p2, x1, x2, exact);
	}

	void init_bounds()
	{
		up.y = get_maxy(upper[ui], upper[ui + 1], up.x, up.x + 1);
		while (ui < upper.size() - 2 && upper[ui + 1].x <= up.x + 1) 
		{
			ui++;
			up.y = std::max(up.y, get_maxy(upper[ui], upper[ui + 1], up.x, up.x + 1));
		}
		if (ui == upper.size() - 2 && upper[ui + 1].x <= up.x + 1) {
			finished_r = true;
		}

		lo.y = get_miny(lower[li], lower[li + 1], lo.x, lo.x + 1);
		while (li < lower.size() - 2 && lower[li + 1].x <= lo.x + 1) 
		{
			li++;
			lo.y = std::min(lo.y, get_miny(lower[li], lower[li + 1], lo.x, lo.x + 1));
		}
		if (li == lower.size() - 2 && lower[li + 1].x <= lo.x + 1) {
			finished_r = true;
		}
	}

public:
	poly_iterator(): is_end(true)
	{}

	poly_iterator(const std::vector<Point> &points): is_end(false), finished(false), finished_r(false)
	{
		int left = std::min_element(points.begin(), points.end()) - points.begin(),
			right = std::max_element(points.begin(), points.end()) - points.begin();

		for (int i = left; ; i = (i + 1) % points.size())
		{
			lower.push_back(points[i]);
			if (i == right)
			{
				break;
			}
		}

		for (int i = right; ; i = (i + 1) % points.size())
		{
			upper.push_back(points[i]);
			if (i == left)
			{
				break;
			}
		}
		std::reverse(upper.begin(), upper.end());

		init();
	}

	bool operator==(const poly_iterator &i) const
	{
		return is_end ? (i.is_end ? true : i.finished) : (i.is_end ? finished : false);
	}

	bool operator!=(const poly_iterator &i) const
	{
		return !((*this) == i);
	}

	poly_iterator& operator++()
	{
		if (curr < up)
		{
			curr.y++;
			return (*this);
		}
		
		finished = finished_r;
		up.x++;
		lo.x++;
		init_bounds();
		curr = lo;
		return (*this);
	}
		
	const Cell& operator*() const
	{
		return curr;
	}
};

#endif